Add back timsort key function handling (bug#69709)
authorMattias Engdegård <mattiase@acm.org>
Mon, 18 Mar 2024 18:56:20 +0000 (19:56 +0100)
committerMattias Engdegård <mattiase@acm.org>
Fri, 29 Mar 2024 10:39:38 +0000 (11:39 +0100)
commita52f1121a3589af8f89828e04d66f1215c361bcf
treee0ee847774d45b3efa7376eefd775e43a30bcf0f
parent1232ab31c656b8564984a758957466f90ac10501
Add back timsort key function handling (bug#69709)

The original timsort code did provide for a key (accessor) function
along with the necessary storage management, but we dropped it because
our `sort` function didn't need it.

Now it's been put back since it seems that it will come in handy after all.

* src/fns.c (sort_list, sort_vector, Fsort): Pass Qnil as key function
to tim_sort.
* src/sort.c (reverse_slice, sortslice_copy)
(sortslice_copy_incr, sortslice_copy_decr, sortslice_memcpy)
(sortslice_memmove, sortslice_advance): New functions.
(sortslice): New type.
(struct stretch, struct reloc, merge_state)
(binarysort, merge_init, merge_markmem, cleanup_mem)
(merge_register_cleanup, merge_getmem, merge_lo, merge_hi, merge_at)
(found_new_run, reverse_sortslice, resolve_fun, tim_sort):
Merge back previously discarded parts from the upstreams timsort code
that dealt with key functions, and adapt them to fit in.
src/fns.c
src/lisp.h
src/sort.c